|
|
Extending Partial Representations of Graphs
Klavík, Pavel ; Kratochvíl, Jan (vedoucí práce) ; Fiala, Jiří (oponent)
V této práci se zabýváme geometrickými průnikovými reprezentacemi grafů. Pro danou třídu se známý problém rozpoznávání ptá, jestli graf na vstupu náleží do této třídy. Studujeme zobecnění tohoto problému nazvané rozšiřování částečných reprezen- tací. Vstup je tvořen grafem spolu s částečnou reprezentací, jinými slovy část grafu je předkreslena. Problém se ptá, jestli je možné tuto částečnou reprezentaci rozšířit na reprezentaci celého grafu. Tento problém studujeme pro třídy intervalových grafů, vlastních intervalových grafů, jednotkových intervalových grafů a chordálních grafˇu (ve formě reprezentací jako podstromy ve stromě). Popisujeme lineární algoritmy pro první dvě třídy a téměř kvadratický algoritmus pro jednotkové intervalové grafy. Pro chordální grafy uvažujeme různé verze problému a ukazujeme, že skoro všechny jsou NP-úplné. Přestože třídy vlastních a jednotkových intervalových grafů jsou si rovny, problém rozšiřování částečných reprezentací je rozlišuje. Jednotkové intervalové grafy kladou dodatečné podmínky týkající se přesných pozic intervalů. V práci popisujeme novou strukturu jednotkových intervalových reprezentací, která umožňuje tyto dodatečné...
|
|
|
Extending Partial Representations of Graphs
Klavík, Pavel
V této práci se zabýváme geometrickými průnikovými reprezentacemi grafů. Pro danou třídu se známý problém rozpoznávání ptá, jestli graf na vstupu náleží do této třídy. Studujeme zobecnění tohoto problému nazvané rozšiřování částečných reprezen- tací. Vstup je tvořen grafem spolu s částečnou reprezentací, jinými slovy část grafu je předkreslena. Problém se ptá, jestli je možné tuto částečnou reprezentaci rozšířit na reprezentaci celého grafu. Tento problém studujeme pro třídy intervalových grafů, vlastních intervalových grafů, jednotkových intervalových grafů a chordálních grafˇu (ve formě reprezentací jako podstromy ve stromě). Popisujeme lineární algoritmy pro první dvě třídy a téměř kvadratický algoritmus pro jednotkové intervalové grafy. Pro chordální grafy uvažujeme různé verze problému a ukazujeme, že skoro všechny jsou NP-úplné. Přestože třídy vlastních a jednotkových intervalových grafů jsou si rovny, problém rozšiřování částečných reprezentací je rozlišuje. Jednotkové intervalové grafy kladou dodatečné podmínky týkající se přesných pozic intervalů. V práci popisujeme novou strukturu jednotkových intervalových reprezentací, která umožňuje tyto dodatečné...
|
|
|
Extending Partial Representations of Graphs
Klavík, Pavel
V této práci se zabýváme geometrickými průnikovými reprezentacemi grafů. Pro danou třídu se známý problém rozpoznávání ptá, jestli graf na vstupu náleží do této třídy. Studujeme zobecnění tohoto problému nazvané rozšiřování částečných reprezen- tací. Vstup je tvořen grafem spolu s částečnou reprezentací, jinými slovy část grafu je předkreslena. Problém se ptá, jestli je možné tuto částečnou reprezentaci rozšířit na reprezentaci celého grafu. Tento problém studujeme pro třídy intervalových grafů, vlastních intervalových grafů, jednotkových intervalových grafů a chordálních grafˇu (ve formě reprezentací jako podstromy ve stromě). Popisujeme lineární algoritmy pro první dvě třídy a téměř kvadratický algoritmus pro jednotkové intervalové grafy. Pro chordální grafy uvažujeme různé verze problému a ukazujeme, že skoro všechny jsou NP-úplné. Přestože třídy vlastních a jednotkových intervalových grafů jsou si rovny, problém rozšiřování částečných reprezentací je rozlišuje. Jednotkové intervalové grafy kladou dodatečné podmínky týkající se přesných pozic intervalů. V práci popisujeme novou strukturu jednotkových intervalových reprezentací, která umožňuje tyto dodatečné...
|
|
|
Extending Partial Representations of Graphs
Klavík, Pavel ; Kratochvíl, Jan (vedoucí práce) ; Fiala, Jiří (oponent)
V této práci se zabýváme geometrickými průnikovými reprezentacemi grafů. Pro danou třídu se známý problém rozpoznávání ptá, jestli graf na vstupu náleží do této třídy. Studujeme zobecnění tohoto problému nazvané rozšiřování částečných reprezen- tací. Vstup je tvořen grafem spolu s částečnou reprezentací, jinými slovy část grafu je předkreslena. Problém se ptá, jestli je možné tuto částečnou reprezentaci rozšířit na reprezentaci celého grafu. Tento problém studujeme pro třídy intervalových grafů, vlastních intervalových grafů, jednotkových intervalových grafů a chordálních grafˇu (ve formě reprezentací jako podstromy ve stromě). Popisujeme lineární algoritmy pro první dvě třídy a téměř kvadratický algoritmus pro jednotkové intervalové grafy. Pro chordální grafy uvažujeme různé verze problému a ukazujeme, že skoro všechny jsou NP-úplné. Přestože třídy vlastních a jednotkových intervalových grafů jsou si rovny, problém rozšiřování částečných reprezentací je rozlišuje. Jednotkové intervalové grafy kladou dodatečné podmínky týkající se přesných pozic intervalů. V práci popisujeme novou strukturu jednotkových intervalových reprezentací, která umožňuje tyto dodatečné...
|
host ::
RSS.